<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="shortcut icon" href="">
    <title>深度优化</title>
    <style type="text/css">
        body {
            background-color: #eccc68;
        }

        canvas {
            width: 400px;
            height: 300px;
            border: 1px solid black;
        }
    </style>
</head>

<body>
    <h1>深度优化</h1>
    <script type="module">
        // import * as TWO from './two.js'
        import { Scene, Render, Rect, PickContrls, Vector2 } from './two/two.js'
        // import Point from './two.js'
        // import Render from './two.js'
        const width = 400, height = 300, edge = 20
        let cols = ~~((width * 2) / edge) - 1, rows = ~~((height * 2) / edge) - 1

        let render = new Render()
        render.setSize(width, height)
        render.setPixelRatio(2)
        render.setAnimationLoop(animation)
        document.querySelector('body').appendChild(render.domElement)

        const scene = new Scene()
        const colorMap = {
            0: 'hsl(220, 20%, 50%)', // 路
            1: 'hsl(120, 100%, 50%)', // 墙
            2: 'hsl(0, 100%, 50%)',  // 待选
        }
        // scene.add(rect)
        // 0-路, 1-墙, 2-待选
        let map = new Array()
        for (let x = 0; x < cols; ++x) {
            map[x] = new Array()
            for (let y = 0; y < rows; ++y) {
                map[x][y] = 1
                const rect = new Rect(edge - 3, edge - 3)
                rect.setAttribute('stroke', false)
                rect.position.copy({ x: (x + 1) * edge, y: (y + 1) * edge })
                scene.add(rect)
            }
        }
        let x_b = ~~(Math.random() * (cols - 1)) + 1, y_b = ~~(Math.random() * (rows - 1)) + 1
        map[x_b][y_b] = 1

        /*
        const controls = new PickContrls(scene, render.domElement)
        controls.setPixelRatio(2)
        */
        function animation() {
            render.render(scene)
            dig({x: x_b, y: y_b})
            display()
        }

        function display() {
            let index = 0
            for (let x = 0; x < cols; ++x) {
                for (let y = 0; y < rows; ++y) {
                    const rect = scene.children[index++]
                    rect.setAttribute('fillStyle', colorMap[map[x][y]])
                }
            }
        }

        function dig(pos={x: 0, y: 0}) {
            dig_(pos.x, pos.y)
        }

        function dig_(x, y) {
            let rank = 0
            let d = [{x: -1, y: 0}, {x: 0, y: 1}, {x: 1, y: 0}, {x: 0, y: -1}]
/*
*/
            for (let i = 0; i < 4; ++i) {
                let r = ~~(Math.random() * 4)
                let tmp = d[r]
                d[r] = d[3-r]
                d[3-r] = tmp
            }
            for (let i = 0; i < 4; ++i) {
                let dx = x
                let dy = y
                // if (dx)
                let range = 1 + ~~(Math.random() * rank)
                while (range > 0) {
                    dx += d[i].x
                    dy += d[i].y
                    if (dx-1 < 0) break
                    if (dx+1 >= cols) break
                    if (dy-1 < 0) break
                    if (dy+1 >= rows) break
                    if (map[dx][dy] === 0) break
                    let count = 0
                    if (map[dx-1][dy] === 0) count++
                    if (map[dx+1][dy] === 0) count++
                    if (map[dx][dy-1] === 0) count++
                    if (map[dx][dy+1] === 0) count++
                    if (count > 1) break
                    range--
                    map[dx][dy] = 0
                }

                if (range <= 0) {
                    dig_(dx, dy)
                }
            }

        }

    </script>

    <code style="width: 800px; height: 250px">
        <p>深度优先算法</p>
        <p>从起始点出发,四个方向掘进</p>
        <p>每次进入下一区域前,判该区域是否为边界,路,该区域的四个方向为路的区个数大于1</p>
        <p>    1). 下一区域是边界或者结束这个方向的掘进:</p>
        <p>    2). 下一区域四个方向为路的个数大于1,则表明已结束这个方向的掘进</p>
        <p>    3). 下一区域未被连通,且剩余掘进步数大于0,该方向掘进</p>
        <p>    4). 下一区域未被连通,且剩余掘进步数小于等于0,则以该区域为起进行下一轮掘进</p>
        <a href="https://blog.csdn.net/jjwwwww/article/details/82872922">随机迷宫生成算法——深度优先算法</a>
    </code>
</body>

</html>